Home | | Latest | About | Random
# 18 Spanning sets and redundancies.
Let us first make a definition. We say a list (or set) of vectors $v_{1},v_{2},\ldots,v_{k}$ is a **spanning set** for a set of vectors $U$ if $$
U = \operatorname{span} (v_{1},\ldots,v_{k}).
$$
In other words, if we take all possible linear combinations of $v_{1},\ldots,v_{k}$, and together that precisely makes the set $U$, then $v_{1},v_{2},\ldots,v_{k}$ is a spanning set of $U$.
**Example.**
Consider the plane of vectors $P=\{ c_{1} \begin{bmatrix}1\\1\\1\end{bmatrix} + c_{2}\begin{bmatrix}1\\2\\3\end{bmatrix} : c_{1},c_{2} \in \mathbb{R} \}$, then $$
\{\begin{bmatrix}1 \\
1 \\
1\end{bmatrix} , \begin{bmatrix}1\\2\\3\end{bmatrix}\}
$$is a spanning set for $P$. Indeed, the span of those two vectors gives the plane $P$.
**Caution.**
If a set is not "all linear combinations" of some set of vectors, then it has no spanning set! For instance, consider the two lines $$
L_{1} = \{c\begin{bmatrix}1\\2\end{bmatrix}:c\in\mathbb{R}\}
$$ and $$
L_{2} = \{c\begin{bmatrix}1\\2\end{bmatrix} + \begin{bmatrix}1\\0\end{bmatrix}:c\in \mathbb{R}\}
$$Note that $L_{1}$ is a line through the origin, while $L_{2}$ is a translation of $L_{1}$ by $\begin{bmatrix}1\\0\end{bmatrix}$. Here $L_{1}$ has a spanning set, namely $\{\begin{bmatrix}1\\2\end{bmatrix}\}$. But $L_{2}$ **does not have a spanning set!** How come? Despite the fact that we can write $$
L_{2} = \operatorname{span} (\begin{bmatrix}1\\2\end{bmatrix}) + \begin{bmatrix}1\\0\end{bmatrix},
$$there is no spanning set for $L_{2}$. Indeed, if we think that you can find some vectors $v_{1},\ldots,v_{k}$ such that $L_{2}\stackrel{?}= \operatorname{span}(v_{1},\ldots,v_{k})$, notice that in particular the zero vector $\vec 0$ is in $\operatorname{span}(v_{1},\ldots, v_{k})$. However, our line $L_{2}$ does not contain the zero vector! Hence $L_{2}$ is not the span of any set! It is true that $L_{2}$ is a **translation** of the span of some set, but it itself is not a span of some set! Hence $L_{2}$ has no spanning sets.
**Remark.** A set may have many different spanning sets! For instance for the line $$
L = \{c\begin{bmatrix}1\\2\end{bmatrix}:c\in\mathbb{R}\}
$$
- The set $\{\begin{bmatrix}1\\2\end{bmatrix}\}$ is a spanning set for $L$.
- The set $\{\begin{bmatrix}1\\2\end{bmatrix},\begin{bmatrix}2\\4\end{bmatrix} \}$ is also a spanning set for $L$.
- The set $\{\begin{bmatrix}1\\2\end{bmatrix},\begin{bmatrix}2\\4\end{bmatrix},\begin{bmatrix}3\\6\end{bmatrix} \}$ is also a spanning set for $L$.
- The set $\{\begin{bmatrix}1\\2\end{bmatrix},\begin{bmatrix}2\\4\end{bmatrix},\begin{bmatrix}3\\6\end{bmatrix} , \begin{bmatrix}0\\0\end{bmatrix}\}$ is also a spanning set for $L$.
- The set $\{\begin{bmatrix}0\\0\end{bmatrix}\}$ is **NOT** a spanning set for $L$.
So spanning sets in general is not unique.
But this does lead to the question: How do we remove the "redundant" vectors from a spanning set, to get a smaller spanning set that still span the same set?
## Removing "redundancies" from a spanning set.
Let us think about what is it that we want to accomplish. Consider the set $$
\{\begin{bmatrix}1\\2\end{bmatrix},\begin{bmatrix}2\\4\end{bmatrix},\begin{bmatrix}3\\6\end{bmatrix} \},
$$if we remove the vectors $\begin{bmatrix}2\\4\end{bmatrix}$ and $\begin{bmatrix}3\\6\end{bmatrix}$ from this set, we would get a new set **but with the same span**, and the reason is because $\begin{bmatrix}2\\4\end{bmatrix}$ is a **linear combination of a previous vector in this set**, namely, $\begin{bmatrix}1\\2\end{bmatrix}$; and so is $\begin{bmatrix}3\\6\end{bmatrix}$ a linear combination of a previous vector $\begin{bmatrix}1\\2\end{bmatrix}$. Hence $$
\operatorname{span} (\begin{bmatrix}1\\2\end{bmatrix},\cancel{\begin{bmatrix}2\\4\end{bmatrix}},\cancel{\begin{bmatrix}3\\6\end{bmatrix}}) = \operatorname{span} (\begin{bmatrix}1\\2\end{bmatrix}).
$$Ok, so what we need to do is: determine which vector is a linear combination of other vectors in our spanning set, and remove. There are many ways to do it but we should do it systematically, otherwise we might wonder whether we have thrown away something that we may actually need.
To this end, we have the following claim that provides a computational method of determining this
> **Claim. An algorithm to remove redundant vectors from a spanning set.**
> Given $k$ many **column vectors** $v_{1},v_{2},\ldots,v_{k}$ , form the matrix $A=\begin{bmatrix}v_{1}\ |\ v_{2}\ |\cdots| \ v_{k}\end{bmatrix}$ with those as columns. Suppose after row-reducing $A$ to an echelon from $\tilde A$, this echelon form has $r$ many pivots that occurs at columns $i_{1},i_{2},\ldots,i_{r}$. Then $$
\operatorname{span} (v_{1},v_{2},\ldots,v_{k}) = \operatorname{span} (v_{i_{1}},v_{i_{2}},\ldots,v_{i_{r}}).
$$
Let us see how to use it first.
**Example.** Consider the list of vectors $v_{1}=\begin{bmatrix}1\\2\\3\end{bmatrix}, v_{2}=\begin{bmatrix}4\\5\\6\end{bmatrix}, v_{3}=\begin{bmatrix}7\\8\\9\end{bmatrix}, v_{4}=\begin{bmatrix}10\\11\\12\end{bmatrix}$. Let us form a matrix with those as columns and row-reduce to an echelon form, we get $$
\begin{bmatrix} 1 & 4 & 7 & 10 \\
2 & 5 & 8 & 11 \\
3 & 6 & 9 & 12 \end{bmatrix} \stackrel{\text{row}}\sim \begin{bmatrix}1 & 4 & 7 & 10 \\
0 & -3 & -6 & -9 \\
0 & -6 & -12 & -18\end{bmatrix} \stackrel{\text{row}}\sim \begin{bmatrix}\colorbox{lightblue}{\(1\)} & 4 & 7 & 10 \\
0 & \colorbox{lightblue}{\(-3\)} & -6 & -9 \\
0 & 0 & 0 & 0\end{bmatrix}
$$where we see that columns 1 and 2 contains pivots, hence by our claim above, we just need to keep the **original** columns 1 and 2, that is $\operatorname{span} (v_{1},v_{2},v_{3},v_{4})=\operatorname{span} (v_1,v_2)$, namely $$
\operatorname{span} (\begin{bmatrix}1\\2\\3\end{bmatrix},\begin{bmatrix}4\\5\\6\end{bmatrix}, \cancel{\begin{bmatrix}7\\8\\9\end{bmatrix}},\cancel{\begin{bmatrix}10\\11\\12\end{bmatrix}}) = \operatorname{span} (\begin{bmatrix}1\\2\\3\end{bmatrix},\begin{bmatrix}4\\5\\6\end{bmatrix}).
$$
**Caution.** A **common mistake** is to use the columns in the echelon form to form the span, which is not correct, that is, in this example we **do not have** $$
\operatorname{span} (\begin{bmatrix}1\\2\\3\end{bmatrix},\begin{bmatrix}4\\5\\6\end{bmatrix}, {\begin{bmatrix}7\\8\\9\end{bmatrix}},{\begin{bmatrix}10\\11\\12\end{bmatrix}}) \neq \operatorname{span} (\begin{bmatrix}1\\0\\0\end{bmatrix},\begin{bmatrix}4\\-3\\0\end{bmatrix})!
$$Just look at the third entry of these vectors!
**Caution.**
Notice the sets $$
\{\begin{bmatrix}1\\2\\3\end{bmatrix},\begin{bmatrix}4\\5\\6\end{bmatrix}, {\begin{bmatrix}7\\8\\9\end{bmatrix}},{\begin{bmatrix}10\\11\\12\end{bmatrix}}\} \neq \{\begin{bmatrix}1\\2\\3\end{bmatrix},\begin{bmatrix}4\\5\\6\end{bmatrix}\}
$$are different, but their spans $$
\operatorname{span} (\begin{bmatrix}1\\2\\3\end{bmatrix},\begin{bmatrix}4\\5\\6\end{bmatrix}, {\begin{bmatrix}7\\8\\9\end{bmatrix}},{\begin{bmatrix}10\\11\\12\end{bmatrix}}) = \operatorname{span} (\begin{bmatrix}1\\2\\3\end{bmatrix},\begin{bmatrix}4\\5\\6\end{bmatrix}).
$$are the same!
**Example.** Suppose we have some column vectors $v_{1},v_{2},v_{3},v_{4},v_{5},v_{6}$, and upon row reducing a matrix with those as columns to an echelon form, we get $$
\begin{bmatrix} \\
v_{1} & v_{2} & v_{3} & v_{4} & v_{5} & v_{6} \\
\ \end{bmatrix} \stackrel{\text{row}}\sim \begin{bmatrix}\colorbox{lightblue}{\(2\)} & 1 & 0 & -2 & 2 & 3 \\
0 & \colorbox{lightblue}{\(5\)} & 3 & 7 & 1 & 0\\
0 & 0 & 0 & \colorbox{lightblue}{\(-3\)} & 8 & 2\end{bmatrix}
$$then by our claim above we can conclude $$
\operatorname{span} (v_{1},v_{2},\cancel{v_{3}},v_{4},\cancel{v_{5}},\cancel{v_{6}})=\operatorname{span} (v_{1},v_{2},v_{4}).
$$
**Neat! But why is this true?** Let us prove it in [[1 teaching/smc-spring-2024-math-13/linear-algebra-notes/18a-proof-of-the-algorithm-of-removing-redundant-vectors|notes 18a]].